/**
 * 21. Merge Two Sorted Lists
 * https://leetcode.com/problems/merge-two-sorted-lists/
 */
package lc21;

public class Main {
  public static void main(String[] args) {
    ListNode l1 = new ListNode(1);
    ListNode l2 = new ListNode(1);
    l1.next = new ListNode(2);
    l1.next.next = new ListNode(4);
    l2.next = new ListNode(3);
    l2.next.next = new ListNode(4);
    ListNode ln = new Solution().mergeTwoLists(l1, l2);
    while (ln != null) {
      System.out.println(ln.val);
      ln = ln.next;
    }
  }
}

class Solution {
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode start = new ListNode(0);
    ListNode ln = start;
    while (l1 != null && l2 != null) {
      if (l1.val > l2.val) {
        ln.next = new ListNode(l2.val);
        l2 = l2.next;
      } else {
        ln.next = new ListNode(l1.val);
        l1 = l1.next;
      }
      ln = ln.next;
    }

    while (l1 != null) {
      ln.next = new ListNode(l1.val);
      l1 = l1.next;
      ln = ln.next;
    }

    while (l2 != null) {
      ln.next = new ListNode(l2.val);
      l2 = l2.next;
      ln = ln.next;
    }

    return start.next;
  }
}

class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}
